package com.itheima.algorithm.leetcode;

/**
 * @author: TylerZhong
 * @description: 判断回文链表
 */
public class E09Leetcode234 {

    /**
     * 步骤1. 找中间点
     * 步骤2. 中间点后半个链表反转
     * 步骤3. 反转后链表与原链表逐一比较
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode p1 = head; // 慢
        ListNode p2 = head; // 快
        ListNode n1 = null; // 新头
        ListNode o1 = head; // 旧头

        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            // 反转链表
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }

        System.out.println(p1);
        System.out.println(n1);

        if (p2 != null) {
            p1 = p1.next;
        }

        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            p1 = p1.next;
            n1 = n1.next;
        }

//        ListNode middle = p1;
//
//
//        ListNode n1 = null;
//        while (middle != null) {
//            ListNode o2 = middle.next;
//            middle.next = n1;
//            n1 = middle;
//            middle = o2;
//        }
//        ListNode newHead = n1;
//
//
//        while (newHead != null) {
//            if (head.val != newHead.val) {
//                return false;
//            }
//            head = head.next;
//            newHead = newHead.next;
//        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2,3, 1);
//        ListNode head = ListNode.of(1, 2, 1);
//        ListNode head = ListNode.of(1, 2, 3,2,1);
        boolean compare = new E09Leetcode234().isPalindrome(head);
        System.out.println(compare);
    }
}
